package com.wzh.test.greedy;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 * 贪心算法
 * 现在有五个电台，每个电台能覆盖的城市如下：
 * K1   北京，上海，天津
 * K2   广州，北京，深圳
 * K3   成都，上海，杭州
 * K4   上海，天津
 * K5    杭州，大连
 * 要求：找出最少的电台集合，能够覆盖所有的城市
 */
public class GreedyAlgorithm{
    public static void main(String[] args) {
        ArrayList<BroadCast> broadCastList = new ArrayList<>();
        broadCastList.add(new BroadCast("k1",new String[]{"北京","上海","天津"}));
        broadCastList.add(new BroadCast("k2",new String[]{"广州","北京","深圳"}));
        broadCastList.add(new BroadCast("k3",new String[]{"成都","上海","杭州"}));
        broadCastList.add(new BroadCast("k4",new String[]{"上海","天津"}));
        broadCastList.add(new BroadCast("k5",new String[]{"杭州","大连"}));

        Set<BroadCast> result = greed(broadCastList);
        for (BroadCast broadCast : result) {
            System.out.println(broadCast.name);
        }

    }

    public static Set<BroadCast> greed(ArrayList<BroadCast> broadCastList){
        Set<String> leaveCities = new HashSet<>();
        for (BroadCast broadCast : broadCastList) {
            for (String arrCity : broadCast.arrCities) {
                leaveCities.add(arrCity);
            }
        }

        Set<BroadCast> result = new HashSet<>();
        while (leaveCities.size() > 0){
            BroadCast tmpBroadCast = null;
            int maxNum = 0;
            for (BroadCast broadCast : broadCastList) {
                //判断这个电台覆盖了剩余城市中的几个
                int tmpNum = getNum(broadCast.arrCities,leaveCities);
                if(tmpNum > maxNum){
                    tmpBroadCast = broadCast;
                    maxNum = tmpNum;
                }
            }

            if(tmpBroadCast != null){
                result.add(tmpBroadCast);
                //移除
                remove(tmpBroadCast.arrCities,leaveCities);
            }
        }
        return result;
    }

    public static void remove(String[] arrCities,Set<String> leaveCities){
        for (String arrCity : arrCities) {
            leaveCities.remove(arrCity);
        }
    }
    public static int getNum(String[] arrCities,Set<String> leaveCities ){
        int num = 0;
        for (String arrCity : arrCities) {
            if(leaveCities.contains(arrCity)){
                num++;
            }
        }
        return num;
    }
}

class BroadCast{
    public String name;
    public String[] arrCities;

    public BroadCast(String name, String[] arrCities) {
        this.name = name;
        this.arrCities = arrCities;
    }
}
